Can Quantum Computers Outperform Gradient Descent?

Abstract:

Gradient descent is a marvel of an algorithm that allows very efficient optimization in high-dimensional spaces. It was provably the best algorithm for well-structured optimization tasks. such as non-smooth convex optimization in large dimensions. But then came quantum computers with their fancy superpositions, pulling off amazing feats of computation. So questions of the form “Is this the best algorithm we have?” had to be asked all over again.

In this talk we will take a look at gradient descent, at the task of non-smooth convex optimization, and we’ll show that quantum computers can’t improve upon gradient descent in general.

Video

Slides